package com.sheng.leetcode.year2022.month11.day04;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/11/04
 *<p>
 * 754. 到达终点数字<p>
 *<p>
 * 在一根无限长的数轴上，你站在0的位置。终点在target的位置。<p>
 * 你可以做一些数量的移动 numMoves :<p>
 * 每次你可以选择向左或向右移动。<p>
 * 第 i 次移动（从  i == 1 开始，到 i == numMoves ），在选择的方向上走 i 步。<p>
 * 给定整数 target ，返回 到达目标所需的 最小 移动次数(即最小 numMoves ) 。<p>
 *<p>
 * 示例 1:<p>
 * 输入: target = 2<p>
 * 输出: 3<p>
 * 解释:<p>
 * 第一次移动，从 0 到 1 。<p>
 * 第二次移动，从 1 到 -1 。<p>
 * 第三次移动，从 -1 到 2 。<p>
 *<p>
 * 示例 2:<p>
 * 输入: target = 3<p>
 * 输出: 2<p>
 * 解释:<p>
 * 第一次移动，从 0 到 1 。<p>
 * 第二次移动，从 1 到 3 。<p>
 *<p>
 * 提示:<p>
 * -10^9 <= target <= 10^9<p>
 * target != 0<p>
 */
public class LeetCode0754 {

    @Test
    public void test01() {
//        int target = 2;
//        int target = 3;
//        int target = -2;
        int target = 4;
        System.out.println(new Solution().reachNumber(target));
    }
}
class Solution {
    public int reachNumber(int target) {
        /**
         * 1 ± 2 ± 3 ± 4 ± 5 ± ... ± numMoves
         * 假设整数的和为 z ，负数的和的 -f
         * 可得 z + f = (k * (k + 1)) / 2
         * z - f = target
         * 得 2 * f = ((k * (k + 1)) / 2) - target
         * 求最小的 k 的值
         */
        if (target < 0) {
            target = -target;
        }
        int numMoves = 1;
        while (true) {
            int num = numMoves * (numMoves + 1) / 2;
            if (num - target >= 0 && (num - target) % 2 == 0) {
                return numMoves;
            }
            numMoves++;
        }
    }
}
